package cn.suchan.jianzhi.q17_hassubtree;

/**
 * 知识点：树的子结构
 * 题目描述
 * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
 *
 * @author suchan
 * @date 2019/05/27
 */
public class Solution {

    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }

        /**
         * 本来想用前/中/后序遍历的顺序来判断，后来发现是错误的
         */
       /* // 先序遍历
        String root1Str1 = firstTraversal(root1);
        String root2Str1 = firstTraversal(root2);
        // 中序遍历
        String root1Str2 = inOrderTraversal(root1);
        String root2Str2 = inOrderTraversal(root2);
        // 后序遍历
        String root1Str3 = postOrderTraversal(root1);
        String root2Str3 = postOrderTraversal(root2);

        if (root1Str1.contains(root2Str1)
                || root1Str2.contains(root2Str2)
                || root1Str3.contains(root2Str3)) {
            return true;
        }*/
        return isSubTree(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }

    public boolean isSubTree(TreeNode root1, TreeNode root2) {
        if (root2 == null) {
            return true;
        }
        if (root1 == null) {
            return false;
        }
        if (root1.val == root2.val) {
            return isSubTree(root1.left, root2.left) && isSubTree(root1.right, root2.right);
        }
        return false;
    }

    /**
     * 先序排序
     * 根节点->左节点->右节点
     *
     * @param root
     * @return
     */
    public String firstTraversal(TreeNode root) {
        if (root == null) {
            return "";
        }
        String result = "";
        if (root.left != null) {
            result = "," + firstTraversal(root.left);
        }
        result = root.val + result;
        if (root.right != null) {
            result = result + "," + firstTraversal(root.right);
        }
        return result;
    }

    /**
     * 中序遍历
     * 左节点->根节点->右节点
     *
     * @param root
     * @return
     */
    public String inOrderTraversal(TreeNode root) {
        if (root == null) {
            return "";
        }
        String result = String.valueOf(root.val);
        if (root.left != null) {
            result = inOrderTraversal(root.left) + "," + result;
        }
        if (root.right != null) {
            result = result + "," + inOrderTraversal(root.right);
        }
        return result;
    }

    /**
     * 后序遍历
     * 左节点->右节点->根节点
     *
     * @param root
     * @return
     */
    public String postOrderTraversal(TreeNode root) {
        if (root == null) {
            return "";
        }
        String result = "";
        if (root.left != null) {
            result = postOrderTraversal(root.left) + ",";
        }
        if (root.right != null) {
            result = result + postOrderTraversal(root.right) + ",";
        }
        result = result + root.val;
        return result;
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        TreeNode node10 = new TreeNode(10);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node8;
        node4.right = node9;
        node5.left = node10;

        TreeNode node11 = new TreeNode(11);
        TreeNode node12 = new TreeNode(12);
        TreeNode node13 = new TreeNode(13);

        node11.left = node12;
        node11.right = node13;

        Solution solution = new Solution();
        System.out.println("=======先序遍历========");
        System.out.println(solution.firstTraversal(node1));
        System.out.println(solution.firstTraversal(node11));
        System.out.println("=======中序遍历========");
        System.out.println(solution.inOrderTraversal(node1));
        System.out.println(solution.inOrderTraversal(node11));
        System.out.println("=======后序遍历========");
        System.out.println(solution.postOrderTraversal(node1));
        System.out.println(solution.postOrderTraversal(node11));

        System.out.println("=======判断结果========");
        System.out.println(solution.HasSubtree(node1, node11));
    }
}
